package com.cat.dataStructure02;

/**
 *   @description https://leetcode.cn/problems/maximum-number-of-robots-within-budget/
 *   @author 曲大人的喵
 *   @create 2025/10/26 20:20
 *   @since JDK17
 */

public class Solution67 {
    static int N = ((int) (5e4 + 10));
    static int[] deque = new int[N];
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int h = 0, t = 0, ans = 0, n = chargeTimes.length;
        long[] prefix = new long[n + 1];
        for (int l = 0, r = 0; r < n; r++) {
            prefix[r + 1] = prefix[r] + runningCosts[r];    // 前缀和
            while (h < t && chargeTimes[deque[t - 1]] <= chargeTimes[r]) {
                t--;
            }
            deque[t++] = r;
            if (chargeTimes[deque[h]] + (r - l + 1) * (prefix[r + 1] - prefix[l]) > budget) {    // 减小窗口
                if (l == deque[h]) {
                    h++;
                }
                l++;
            } else {
                ans = Math.max(ans, r - l + 1);
            }
        }

        return ans;
    }
}
